565. 数组嵌套

Similar Question

Solution Tips

方案一: 有向图成环

遍历数组，从 i 向 nums[i] 连边，我们可以得到一张有向图。

由于题目保证 nums 中不含有重复的元素，因此有向图中每个点的出度和入度均为 1。

在这种情况下，有向图必然由一个或多个环组成。我们可以遍历 nums，找到节点个数最大的环。

代码实现时需要用一个 vis 数组来标记访问过的节点。

var arrayNesting = function(nums) {
    let ans = 0, n = nums.length;
    const vis = new Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        let cnt = 0;
        while (!vis[i]) {
            vis[i] = true;
            i = nums[i];
            ++cnt;
        }
        ans = Math.max(ans, cnt);
    }
    return ans;
};

方案二: 原地算法优化方案一

利用

nums 中的元素大小在 [0,n−1] 之间这一条件，我们可以省略 vis 数组，改为标记 nums[i]=n，来实现和

vis 数组同样的功能。

把数字放回自己正确的位置, 相当于是 442 的 swap 方案

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        for i in range(n):
            cnt = 0
            while nums[i] < n:
                num = nums[i]
                nums[i] = n
                i = num
                cnt += 1
            ans = max(ans, cnt)
        return ans